#ifndef BSTREE_H
#define BSTREE_H

#include <iomanip>
#include <iostream>
using namespace std;

template<class T>
class BSTNode{
public:
    T m_key;
    BSTNode *m_left;
    BSTNode *m_right;
    BSTNode *m_parent;

    BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r):
               m_key(value),m_parent(p),m_left(l),m_right(r) {}
};

template<class T>
class BSTree
{
public:
    BSTree();
    ~BSTree();

    // 前序遍历"二叉树"
    void preOrder();
    // 中序遍历"二叉树"
    void inOrder();
    // 后序遍历"二叉树"
    void postOrder();

    // (递归实现)查找"二叉树"中键值为key的节点
    BSTNode<T>* search(T key);
    // (非递归实现)查找"二叉树"中键值为key的节点
    BSTNode<T>* iterativeSearch(T key);

    // 查找最小结点：返回最小结点的键值。
    T minimum();
    // 查找最大结点：返回最大结点的键值。
    T maximum();

    // 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
    BSTNode<T>* successor(BSTNode<T> *x);
    // 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
    BSTNode<T>* predecessor(BSTNode<T> *x);

    // 将结点(key为节点键值)插入到二叉树中
    void insert(T key);

    // 删除结点(key为节点键值)
    void remove(T key);

    // 销毁二叉树
    void destroy();

    // 打印二叉树
    void print();

private:
    // 前序遍历"二叉树"
    void preOrder(BSTNode<T>* tree);
    // 中序遍历"二叉树"
    void inOrder(BSTNode<T>* tree);
    // 后序遍历"二叉树"
    void postOrder(BSTNode<T>* tree);

    // (递归实现)查找"二叉树x"中键值为key的节点
    BSTNode<T>* search(BSTNode<T>* x, T key);
    // (非递归实现)查找"二叉树x"中键值为key的节点
    BSTNode<T>* iterativeSearch(BSTNode<T>* x, T key);

    // 查找最小结点：返回tree为根结点的二叉树的最小结点。
    BSTNode<T>* minimum(BSTNode<T>* tree);
    // 查找最大结点：返回tree为根结点的二叉树的最大结点。
    BSTNode<T>* maximum(BSTNode<T>* tree);

    // 将结点(z)插入到二叉树(tree)中
    void insert(BSTNode<T>* &tree, BSTNode<T>* z);

    // 删除二叉树(tree)中的结点(z)，并返回被删除的结点
    BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z);

    // 销毁二叉树
    void destroy(BSTNode<T>* &tree);

    // 打印二叉树
    void print(BSTNode<T>* tree, T key, int direction);

private:
    BSTNode<T> *m_root;
};

template<class T>
BSTree<T>::BSTree() : m_root(NULL)
{

}

template<class T>
BSTree<T>::~BSTree()
{
    destroy();
}

template <class T>
void BSTree<T>::preOrder(BSTNode<T>* tree)
{
    if(tree != NULL)
    {
        cout << tree->m_key << " ";
        preOrder(tree->m_left);
        preOrder(tree->m_right);
    }
}

template<class T>
void BSTree<T>::preOrder()
{
    preOrder(m_root);
}

template <class T>
void BSTree<T>::inOrder(BSTNode<T>* tree)
{
    if(tree != NULL)
    {
        inOrder(tree->m_left);
        cout << tree->m_key << " ";
        inOrder(tree->m_right);
    }
}

template<class T>
void BSTree<T>::inOrder()
{
    inOrder(m_root);
}

template <class T>
void BSTree<T>::postOrder(BSTNode<T>* tree)
{
    if(tree != NULL)
    {
        postOrder(tree->m_left);
        postOrder(tree->m_right);
        cout << tree->m_key << " ";
    }
}

template<class T>
void BSTree<T>::postOrder()
{
    postOrder(m_root);
}

template<class T>
BSTNode<T>* BSTree<T>::search(BSTNode<T>* x, T key)
{
    if(x == NULL || x->m_key == key)
        return x;

    if(x->m_key < key)
        return search(x->m_right, key);
    else
        return search(x->m_left, key);
}

template<class T>
BSTNode<T>* BSTree<T>::search( T key)
{
    return search(m_root, key);
}

template<class T>
BSTNode<T>* BSTree<T>::iterativeSearch(BSTNode<T>* x, T key)
{
   while(x != NULL && x->m_key != key)
   {
       if( key < x->m_key)
           x = x->m_left;
       else
           x = x->m_right;
   }

   return x;
}

template<class T>
BSTNode<T>* BSTree<T>::iterativeSearch( T key)
{
    return iterativeSearch(m_root, key);
}

template<class T>
BSTNode<T>* BSTree<T>::minimum(BSTNode<T>* tree)
{
    if(tree == NULL)
        return tree;

    while(tree->m_left != NULL)
        tree = tree->m_left;

    return tree;
}

template<class T>
T BSTree<T>::minimum()
{
    return minimum(m_root)->m_key;
}

template<class T>
BSTNode<T>* BSTree<T>::maximum(BSTNode<T>* tree)
{
    if(tree == NULL)
        return tree;

    while(tree->m_right != NULL)
        tree = tree->m_right;

    return tree;
}

template<class T>
T BSTree<T>::maximum()
{
    return maximum(m_root)->m_key;
}

template<class T>
BSTNode<T>* BSTree<T>::successor(BSTNode<T> *x)
{
    if(x->m_right != NULL)
        return minimum(x->m_right);

    T cur = x->m_key;
    BSTNode<T> *parent = x->m_parent;
    while(parent != NULL && x == parent->m_right)
    {
        x = parent;
        parent = parent->m_parent;
    }

    if( parent->m_key < cur)
        return NULL;

    return parent;
}

template<class T>
BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x)
{
    if(x->left != NULL)
        return maximum(x->m_left);

    T cur = x->m_key;
    BSTNode<T> *parent = x->m_parent;
    while(parent != NULL && x == parent->m_left)
    {
        x = parent;
        parent = parent->m_parent;
    }

    if( parent->m_key > cur)
        return NULL;

    return parent;
}

template<class T>
void BSTree<T>::insert(BSTNode<T>* &tree, BSTNode<T>* z)
{
    BSTNode<T> *cur = tree;
    BSTNode<T> *tmp = NULL;

    if(tree == NULL)
    {
        tree = z;
        return;
    }

    while(cur != NULL)
    {
        tmp = cur;
        if(z->m_key < cur->m_key)
            cur = cur->m_left;
        else
            cur = cur->m_right;
    }

    cur = tmp;
    z->m_parent = cur;
    if(cur == NULL)
        tree = z;
    else if(z->m_key < cur->m_key)
        cur->m_left = z;
    else
        cur->m_right = z;

}

template<class T>
void BSTree<T>::insert(T key)
{
    BSTNode<T> *tmp = NULL;

    if((tmp = new BSTNode<T>(key, NULL, NULL, NULL)) == NULL)
        return;

    insert(m_root, tmp);
}

template<class T>
BSTNode<T>* BSTree<T>::remove(BSTNode<T>* &tree, BSTNode<T>* z)
{
    BSTNode<T> *parent = NULL;

    /// 叶子结点
    if(z->m_left == NULL && z->m_right == NULL)
    {
        parent = z->m_parent;
        if(parent == NULL) ///< 根结点
        {
            tree = NULL;
        }
        else
        {
            if(parent->m_left == z)
                parent->m_left = NULL;
            else
                parent->m_right = NULL;
        }
    }
    else if( z->m_left != NULL && z->m_right == NULL)
    {
        parent = z->m_parent;
        if(parent == NULL) ///< 根结点
        {
            tree = z->m_left;
            z->m_parent = NULL;
        }
        else
        {
            z->m_left->m_parent = parent;
            parent->m_left = z->m_left;
        }

    }
    else if( z->m_left == NULL && z->m_right != NULL)
    {
        parent = z->m_parent;
        if(parent == NULL) ///< 根结点
        {
            tree = z->m_right;
            z->m_parent = NULL;
        }
        else
        {
            z->m_right->m_parent = parent;
            parent->m_right = z->m_right;
        }
    }
    else
    {
        parent = z->m_parent;
        BSTNode<T> *x = successor(z);
        if(x->m_right != NULL)
        {
           // x->m_right->m_parent = x->m_parent;
            if(x == x->m_parent->m_left )
            {
                x->m_parent->m_left = x->m_right;
            }
            else
            {
                x->m_parent->m_right = x->m_right;
            }
            x->m_right->m_parent = x->m_parent;
        }
        if(parent == NULL) ///< 根结点
        {
            tree = x;

        }
        else
        {
            if(z == z->m_parent->m_left)
                z->m_parent->m_left = x;
            else
                z->m_parent->m_right = x;
        }
        x->m_left = z->m_left;
        x->m_right = z->m_right;
        x->m_parent = parent;
    }

    return z;
}

template <class T>
void BSTree<T>::remove(T key)
{
    BSTNode<T> *z, *node;

    if ((z = search(m_root, key)) != NULL)
        if ( (node = remove(m_root, z)) != NULL)
            delete node;
}


template <class T>
void BSTree<T>::destroy(BSTNode<T>* &tree)
{
    if (tree==NULL)
        return ;

    if (tree->m_left != NULL)
        return destroy(tree->m_left);
    if (tree->m_right != NULL)
        return destroy(tree->m_right);

    delete tree;
    tree=NULL;
}

template <class T>
void BSTree<T>::destroy()
{
    destroy(m_root);
}


template <class T>
void BSTree<T>::print(BSTNode<T>* tree, T key, int direction)
{
    if(tree != NULL)
    {
        if(direction==0)
            cout << setw(2) << tree->m_key << " is root" << endl;
        else
            cout << setw(2) << tree->m_key << " is " << setw(2) << key << "'s "  << setw(12) << (direction==1?"right child" : "left child") << endl;

        print(tree->m_left, tree->m_key, -1);
        print(tree->m_right,tree->m_key,  1);
    }
}

template <class T>
void BSTree<T>::print()
{
    if (m_root != NULL)
        print(m_root, m_root->m_key, 0);
}

#endif // BSTREE_H
























